In the "100 game" two players take turns adding, to a running total, any integer from 1 to 10. The player who first causes the running total to reach or exceed 100 wins.
What if we change the game so that players cannot re-use integers?
For example, two players might take turns drawing from a common pool of numbers from 1 to 15 without replacement until they reach a total >= 100.
Given two integers maxChoosableInteger and desiredTotal, return true if the first player to move can force a win, otherwise, return false. Assume both players play optimally.
Input: maxChoosableInteger = 10, desiredTotal = 11 Output: false Explanation: No matter which integer the first player choose, the first player will lose. The first player can choose an integer from 1 up to 10. If the first player choose 1, the second player can only choose integers from 2 up to 10. The second player will win by choosing 10 and get a total = 11, which is >= desiredTotal. Same with other integers chosen by the first player, the second player will always win.
Input: maxChoosableInteger = 10, desiredTotal = 0 Output: true
Input: maxChoosableInteger = 10, desiredTotal = 1 Output: true
1 <= maxChoosableInteger <= 200 <= desiredTotal <= 300
fromfunctoolsimportcacheclassSolution: defcanIWin(self, maxChoosableInteger: int, desiredTotal: int) ->bool: @cachedefcanIWinWithUsed(usedmask: int) ->bool: total=sum(i+1foriinrange(maxChoosableInteger) if (usedmask>>i) &1==1) foriinrange(maxChoosableInteger): if (usedmask>>i) &1==0: iftotal+i+1>=desiredTotalornotcanIWinWithUsed(usedmask| (1<<i)): returnTruereturnFalsereturnsum(range(1, maxChoosableInteger+1)) >=desiredTotalandcanIWinWithUsed(0)